package com.yubest;

/**
 * 给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
 * <p>
 * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
 * <p>
 * 返回一对观光景点能取得的最高分。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：values = [8,1,5,2,6]
 * 输出：11
 * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
 * 示例 2：
 * <p>
 * 输入：values = [1,2]
 * 输出：2
 *
 * <p>
 * 提示：
 * <p>
 * 2 <= values.length <= 5 * 10^4
 * 1 <= values[i] <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-sightseeing-pair
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/12/30 17:28
 */
public class P1014 {

    public static void main(String[] args) {
        new Solution1014().maxScoreSightseeingPair(new int[]{8, 1, 5, 2, 6});
    }
}

class Solution1014 {

    /**
     * 思路：
     * 1、values[i] + values[j] + i - j 可以写为 (values[i] + i) + (values[j] - j)
     * 2、当以 j 为结束点时，求 max{values[0 ... j - 1] + (0 ... j - 1)} 的值，即可以得到最大值，由此动态规划方程为：
     * dp[j] = (values[j] - j) + max{values[0 ... j - 1] + (0 ... j - 1)}
     *
     * @param values
     * @return
     */
    public int maxScoreSightseeingPair(int[] values) {
        int maxX = values[0], max = 0;
        int cur;
        for (int i = 1; i < values.length; i++) {
            cur = values[i] - i + maxX;
            max = Math.max(max, cur);
            maxX = Math.max(maxX, values[i] + i);
        }
        return max;
    }
}
